<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  <title>哈希图 and 移动窗口 | Miki&#39;s blog</title>
  <meta name="keywords" content=" 算法 ">
  <meta name="description" content="哈希图 and 移动窗口 | Miki&#39;s blog">
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
<meta name="description" content="keywords: author: Miki language: zh-CN timezone:">
<meta property="og:type" content="website">
<meta property="og:title" content="标签">
<meta property="og:url" content="http://mikiblog.online/tags/index.html">
<meta property="og:site_name" content="Miki&#39;s blog">
<meta property="og:description" content="keywords: author: Miki language: zh-CN timezone:">
<meta property="og:locale" content="en_US">
<meta property="article:published_time" content="2020-02-22T01:48:02.000Z">
<meta property="article:modified_time" content="2020-02-22T01:50:40.651Z">
<meta property="article:author" content="Miki Zhu">
<meta name="twitter:card" content="summary">


<link rel="icon" href="/img/1.jpg">

<link href="/css/style.css?v=1.0.1" rel="stylesheet">

<link href="/css/hl_theme/atom-dark.css?v=1.0.1" rel="stylesheet">

<link href="//cdn.bootcss.com/animate.css/3.5.2/animate.min.css" rel="stylesheet">
<link href="//cdn.bootcss.com/font-awesome/4.7.0/css/font-awesome.min.css" rel="stylesheet">

<script src="//cdn.bootcss.com/jquery/2.2.4/jquery.min.js"></script>
<script src="/js/jquery.autocomplete.min.js?v=1.0.1" ></script>

<script src="//cdn.bootcss.com/highlight.js/9.12.0/highlight.min.js"></script>
<script>
    hljs.initHighlightingOnLoad();
</script>

<script src="//cdn.bootcss.com/nprogress/0.2.0/nprogress.min.js"></script>



<script src="/js/iconfont.js?v=1.0.1" ></script>

<meta name="generator" content="Hexo 4.2.0"></head>
<div style="display: none">
  <input class="theme_disqus_on" value="false">
  <input class="theme_preload_comment" value="false">
  <input class="theme_blog_path" value="">
</div>

<body>
<aside class="nav">
    <div class="nav-left">
        <a href="/" class="avatar_target">
    <img class="avatar" src="/img/头像.jpg" />
</a>
<div class="author">
    <span>Miki Zhu</span>
</div>

<div class="icon">
    
        
    
        
        <a title="email" href="mailto:747876457@qq.com" target="_blank">
            
                <svg class="iconfont-svg" aria-hidden="true">
                    <use xlink:href="#icon-email"></use>
                </svg>
            
        </a>
        
    
        
        <a title="qq" href="http://wpa.qq.com/msgrd?v=3&uin=747876457&site=qq&menu=yes" target="_blank">
            
                <svg class="iconfont-svg" aria-hidden="true">
                    <use xlink:href="#icon-qq"></use>
                </svg>
            
        </a>
        
    
</div>




<ul>
    <li><div class="all active">全部文章<small>(29)</small></div></li>
    
        
            
            <li><div data-rel="机器学习">机器学习<small>(7)</small></div>
                
            </li>
            
        
    
        
            
            <li><div data-rel="机器学习实战">机器学习实战<small>(3)</small></div>
                
            </li>
            
        
    
        
            
            <li><div data-rel="项目实战">项目实战<small>(4)</small></div>
                
            </li>
            
        
    
        
            
            <li><div data-rel="博客搭建">博客搭建<small>(2)</small></div>
                
            </li>
            
        
    
        
            
            <li><div data-rel="算法">算法<small>(3)</small></div>
                
            </li>
            
        
    
        
            
            <li><div data-rel="python教程">python教程<small>(1)</small></div>
                
            </li>
            
        
    
        
            
            <li><div data-rel="学习网站推荐">学习网站推荐<small>(1)</small></div>
                
            </li>
            
        
    
        
            
            <li><div data-rel="考研经验">考研经验<small>(1)</small></div>
                
            </li>
            
        
    
</ul>
<div class="left-bottom">
    <div class="menus">
    
    
    
    
    </div>
    <div><a class="about  " target="_blank" href="/about">关于</a></div>
</div>
<input type="hidden" id="yelog_site_posts_number" value="29">
<input type="hidden" id="yelog_site_word_count" value="62.1k">
<div style="display: none">
    <span id="busuanzi_value_site_uv"></span>
    <span id="busuanzi_value_site_pv"></span>
</div>

    </div>
    <div class="nav-right">
        <div class="friends-area">
    <div class="friends-title">
        友情链接
        <i class="back-title-list"></i>
    </div>
    <div class="friends-content">
        <ul>
            
        </ul>
    </div>
</div>
        <div class="title-list">
    <form onkeydown="if(event.keyCode === 13){return false;}">
        <input id="local-search-input" class="search" type="text" placeholder="Search..." />
        <i class="cross"></i>
        <span>
            <label for="tagswitch">Tags:</label>
            <input id="tagswitch" type="checkbox" style="display: none" />
            <i id="tagsWitchIcon"></i>
        </span>
    </form>
    <div class="tags-list">
    
    <li class="article-tag-list-item">
        <a class="color5">机器学习</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color3">算法</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color5">博客搭建</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color2">python</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color5">网站推荐</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color5">考研经验</a>
    </li>
    
    <div class="clearfix"></div>
</div>

    
    <nav id="title-list-nav">
        
        <a id="top" class="python教程 "
           href="/2020/04/03/python%E9%9D%A2%E8%AF%95%E9%A2%98/"
           data-tag="python"
           data-author="" >
            <span class="post-title" title="python面试题(不定期更新)">python面试题(不定期更新)</span>
            <span class="post-date" title="2020-04-03 21:14:43">2020/04/03</span>
        </a>
        
        <a id="top" class="考研经验 "
           href="/2020/02/20/%E8%80%83%E7%A0%94%E5%88%9D%E8%AF%95%E7%BB%8F%E9%AA%8C/"
           data-tag="考研经验"
           data-author="" >
            <span class="post-title" title="考研初试经验">考研初试经验</span>
            <span class="post-date" title="2020-02-20 19:33:48">2020/02/20</span>
        </a>
        
        <a  class="机器学习实战 "
           href="/2020/04/19/%E9%80%BB%E8%BE%91%E5%9B%9E%E5%BD%92%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0/"
           data-tag="机器学习"
           data-author="" >
            <span class="post-title" title="逻辑回归代码实现">逻辑回归代码实现</span>
            <span class="post-date" title="2020-04-19 21:09:25">2020/04/19</span>
        </a>
        
        <a  class="机器学习 "
           href="/2020/04/14/%E9%A9%AC%E5%B0%94%E5%8F%AF%E5%A4%AB%E9%93%BE/"
           data-tag="机器学习"
           data-author="" >
            <span class="post-title" title="马尔可夫链">马尔可夫链</span>
            <span class="post-date" title="2020-04-14 19:09:29">2020/04/14</span>
        </a>
        
        <a  class="机器学习实战 "
           href="/2020/04/14/%E5%86%B3%E7%AD%96%E6%A0%91%E5%AE%9E%E6%88%98%E9%9A%90%E5%BD%A2%E7%9C%BC%E9%95%9C%E5%88%86%E7%B1%BB/"
           data-tag="机器学习"
           data-author="" >
            <span class="post-title" title="决策树实战隐形眼镜分类">决策树实战隐形眼镜分类</span>
            <span class="post-date" title="2020-04-14 10:49:40">2020/04/14</span>
        </a>
        
        <a  class="机器学习实战 "
           href="/2020/04/12/KNN%E5%AE%9E%E6%88%98%E4%B9%8B%E6%B5%B7%E4%BC%A6%E7%BA%A6%E4%BC%9A/"
           data-tag="机器学习"
           data-author="" >
            <span class="post-title" title="KNN实战之海伦约会">KNN实战之海伦约会</span>
            <span class="post-date" title="2020-04-12 08:22:12">2020/04/12</span>
        </a>
        
        <a  class="博客搭建 "
           href="/2020/04/08/hexo-%E4%B8%BB%E9%A2%98%E6%B7%BB%E5%8A%A0%E8%AF%84%E8%AE%BA/"
           data-tag="博客搭建"
           data-author="" >
            <span class="post-title" title="hexo 主题添加评论">hexo 主题添加评论</span>
            <span class="post-date" title="2020-04-08 21:43:26">2020/04/08</span>
        </a>
        
        <a  class="项目实战 "
           href="/2020/03/30/%E6%98%8E%E5%A4%A9%E4%BC%9A%E4%B8%8B%E9%9B%A8%E5%90%97%EF%BC%9F/"
           data-tag="机器学习"
           data-author="" >
            <span class="post-title" title="明天会下雨吗？">明天会下雨吗？</span>
            <span class="post-date" title="2020-03-30 11:25:31">2020/03/30</span>
        </a>
        
        <a  class="项目实战 "
           href="/2020/03/23/%E5%86%B3%E7%AD%96%E6%A0%91%E5%AE%9E%E7%8E%B0Titanic-%E9%87%8D%E8%A6%81/"
           data-tag="机器学习"
           data-author="" >
            <span class="post-title" title="决策树实现Titanic(重要)">决策树实现Titanic(重要)</span>
            <span class="post-date" title="2020-03-23 17:09:05">2020/03/23</span>
        </a>
        
        <a  class="项目实战 "
           href="/2020/03/21/Titanic-%E9%A1%B9%E7%9B%AE%E8%AF%A6%E8%A7%A3/"
           data-tag="机器学习"
           data-author="" >
            <span class="post-title" title="Titanic 项目详解">Titanic 项目详解</span>
            <span class="post-date" title="2020-03-21 14:07:20">2020/03/21</span>
        </a>
        
        <a  class="项目实战 "
           href="/2020/03/19/kaggle%E9%A1%B9%E7%9B%AE%E5%AE%9E%E6%88%98/"
           data-tag="机器学习"
           data-author="" >
            <span class="post-title" title="kaggle项目实战，Titanic analysis">kaggle项目实战，Titanic analysis</span>
            <span class="post-date" title="2020-03-19 10:08:13">2020/03/19</span>
        </a>
        
        <a  class=""
           href="/2020/03/17/Pytorch-%E6%90%AD%E5%BB%BA%E7%A5%9E%E7%BB%8F%E7%BD%91%E7%BB%9C/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="Pytorch 搭建神经网络">Pytorch 搭建神经网络</span>
            <span class="post-date" title="2020-03-17 14:56:16">2020/03/17</span>
        </a>
        
        <a  class=""
           href="/2020/03/16/CNN%E5%8E%9F%E7%90%86/"
           data-tag="机器学习"
           data-author="" >
            <span class="post-title" title="CNN">CNN</span>
            <span class="post-date" title="2020-03-16 09:11:00">2020/03/16</span>
        </a>
        
        <a  class=""
           href="/2020/03/14/%E9%9A%8F%E6%9C%BA%E6%A3%AE%E6%9E%97%E5%92%8Ck%E5%9D%87%E5%80%BC/"
           data-tag="机器学习"
           data-author="" >
            <span class="post-title" title="random forest and k means">random forest and k means</span>
            <span class="post-date" title="2020-03-14 16:29:22">2020/03/14</span>
        </a>
        
        <a  class=""
           href="/2020/03/13/%E6%94%AF%E6%8C%81%E5%90%91%E9%87%8F%E6%9C%BA%E7%AE%97%E6%B3%95/"
           data-tag="机器学习"
           data-author="" >
            <span class="post-title" title="支持向量机">支持向量机</span>
            <span class="post-date" title="2020-03-13 20:53:20">2020/03/13</span>
        </a>
        
        <a  class=""
           href="/2020/03/11/Matplotlab/"
           data-tag="机器学习"
           data-author="" >
            <span class="post-title" title="Matplotlab">Matplotlab</span>
            <span class="post-date" title="2020-03-11 10:13:20">2020/03/11</span>
        </a>
        
        <a  class=""
           href="/2020/03/10/pandas/"
           data-tag="机器学习"
           data-author="" >
            <span class="post-title" title="pandas">pandas</span>
            <span class="post-date" title="2020-03-10 09:20:27">2020/03/10</span>
        </a>
        
        <a  class=""
           href="/2020/03/09/logical-regression/"
           data-tag="机器学习"
           data-author="" >
            <span class="post-title" title="logical regression">logical regression</span>
            <span class="post-date" title="2020-03-09 20:30:33">2020/03/09</span>
        </a>
        
        <a  class="学习网站推荐 "
           href="/2020/03/08/%E5%AD%A6%E4%B9%A0%E7%BD%91%E7%AB%99%E6%88%96%E5%B7%A5%E5%85%B7%E6%8E%A8%E8%8D%90/"
           data-tag="网站推荐"
           data-author="" >
            <span class="post-title" title="学习网站或工具推荐">学习网站或工具推荐</span>
            <span class="post-date" title="2020-03-08 20:44:55">2020/03/08</span>
        </a>
        
        <a  class="机器学习 "
           href="/2020/03/08/%E8%B4%9D%E5%8F%B6%E6%96%AF%E5%88%86%E6%9E%90/"
           data-tag="机器学习"
           data-author="" >
            <span class="post-title" title="贝叶斯分析">贝叶斯分析</span>
            <span class="post-date" title="2020-03-08 20:11:15">2020/03/08</span>
        </a>
        
        <a  class="机器学习 "
           href="/2020/03/08/numpy/"
           data-tag="机器学习"
           data-author="" >
            <span class="post-title" title="numpy的使用">numpy的使用</span>
            <span class="post-date" title="2020-03-08 19:15:54">2020/03/08</span>
        </a>
        
        <a  class="机器学习 "
           href="/2020/03/07/%E5%86%B3%E7%AD%96%E6%A0%91/"
           data-tag="机器学习"
           data-author="" >
            <span class="post-title" title="决策树">决策树</span>
            <span class="post-date" title="2020-03-07 19:27:38">2020/03/07</span>
        </a>
        
        <a  class="机器学习 "
           href="/2020/03/06/K-%E8%BF%91%E9%82%BB%E7%AE%97%E6%B3%95/"
           data-tag="算法"
           data-author="" >
            <span class="post-title" title="K-近邻算法">K-近邻算法</span>
            <span class="post-date" title="2020-03-06 20:18:19">2020/03/06</span>
        </a>
        
        <a  class="算法 "
           href="/2020/03/05/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/"
           data-tag="算法"
           data-author="" >
            <span class="post-title" title="排序算法">排序算法</span>
            <span class="post-date" title="2020-03-05 19:41:32">2020/03/05</span>
        </a>
        
        <a  class="算法 "
           href="/2020/03/04/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6/"
           data-tag="算法"
           data-author="" >
            <span class="post-title" title="数据结构与时间复杂度">数据结构与时间复杂度</span>
            <span class="post-date" title="2020-03-04 21:00:32">2020/03/04</span>
        </a>
        
        <a  class="机器学习 "
           href="/2020/03/04/%E6%9C%BA%E5%99%A8%E5%AD%A6%E4%B9%A0%E6%95%B0%E5%AD%A6%E5%9F%BA%E7%A1%80/"
           data-tag="机器学习"
           data-author="" >
            <span class="post-title" title="机器学习数学基础">机器学习数学基础</span>
            <span class="post-date" title="2020-03-04 16:48:34">2020/03/04</span>
        </a>
        
        <a  class="算法 "
           href="/2020/03/03/leetcode%E7%AE%97%E6%B3%95%E7%BB%83%E4%B9%A0/"
           data-tag="算法"
           data-author="" >
            <span class="post-title" title="哈希图 and 移动窗口">哈希图 and 移动窗口</span>
            <span class="post-date" title="2020-03-03 18:49:52">2020/03/03</span>
        </a>
        
        <a  class="机器学习 "
           href="/2020/03/01/%E6%9C%BA%E5%99%A8%E5%AD%A6%E4%B9%A0%E5%9F%BA%E6%9C%AC%E6%9C%AF%E8%AF%AD/"
           data-tag="机器学习"
           data-author="" >
            <span class="post-title" title="1 零基础学机器学习">1 零基础学机器学习</span>
            <span class="post-date" title="2020-03-01 20:23:40">2020/03/01</span>
        </a>
        
        <a  class="博客搭建 "
           href="/2020/02/20/Windows%E7%B3%BB%E7%BB%9F%E4%B8%8B%E7%94%A8hexo%E6%90%AD%E5%BB%BA%E4%B8%AA%E4%BA%BA%E5%8D%9A%E5%AE%A2/"
           data-tag="博客搭建"
           data-author="" >
            <span class="post-title" title="Windows系统下用hexo搭建个人博客">Windows系统下用hexo搭建个人博客</span>
            <span class="post-date" title="2020-02-20 13:15:25">2020/02/20</span>
        </a>
        
    </nav>
</div>
    </div>
    <div class="hide-list">
        <div class="semicircle">
            <div class="brackets first"><</div>
            <div class="brackets">&gt;</div>
        </div>
    </div>
</aside>
<div class="post">
    <div class="pjax">
        <article id="post-leetcode算法练习" class="article article-type-post" itemscope itemprop="blogPost">
    
        <h1 class="article-title">哈希图 and 移动窗口</h1>
    
    <div class="article-meta">
        
        
        
        <span class="book">
            
                <a  data-rel="算法">算法</a>
            
        </span>
        
        
        <span class="tag">
            
            <a class="color3">算法</a>
            
        </span>
        
    </div>
    <div class="article-meta">
        
        创建时间:<time class="date" title='更新时间: 2020-03-09 10:30:11'>2020-03-03 18:49</time>
        
    </div>
    <div class="article-meta">
        
        <span>字数:1.5k</span>
        
        
        <span id="busuanzi_container_page_pv">
            阅读:<span id="busuanzi_value_page_pv">
                <span class="count-comment">
                    <span class="spinner">
                      <div class="cube1"></div>
                      <div class="cube2"></div>
                    </span>
                </span>
            </span>
        </span>
        
        
        <span class="top-comment" title="跳转至评论区">
            <a href="#comments">
                评论:<span class="count-comment">
                    <span class="spinner">
                      <div class="cube1"></div>
                      <div class="cube2"></div>
                    </span>
                </span>
            </a>
        </span>
        
    </div>
    
    <div class="toc-ref">
    
        <ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#题目1-两数之和"><span class="toc-text"> 题目1 两数之和</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#题目"><span class="toc-text"> 题目</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#解答"><span class="toc-text"> 解答</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#算法-哈希字典查找"><span class="toc-text"> 算法 哈希字典查找</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#知识补充python字典与哈希的关系"><span class="toc-text"> 知识补充，python字典与哈希的关系</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#题目三-无重复字符的最长字符串"><span class="toc-text"> 题目三 无重复字符的最长字符串</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#问题"><span class="toc-text"> 问题</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#算法-移动窗口"><span class="toc-text"> 算法 移动窗口</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#错误解法"><span class="toc-text"> 错误解法</span></a></li></ol></li></ol>
    
<style>
    .left-col .switch-btn,
    .left-col .switch-area {
        display: none;
    }
    .toc-level-3 i,
    .toc-level-3 ol {
        display: none !important;
    }
</style>
</div>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h2 id="题目1-两数之和"><a class="markdownIt-Anchor" href="#题目1-两数之和"></a> 题目1 两数之和</h2>
<h3 id="题目"><a class="markdownIt-Anchor" href="#题目"></a> 题目</h3>
<p>给定一个整数数组 <code>nums</code> 和一个目标值 <code>target</code>，请你在该数组中找出和为目标值的那 <strong>两个</strong> 整数，并返回他们的数组下标。</p>
<p>你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。</p>
<p><strong>示例:</strong></p>
<pre class="highlight"><code class="">给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
</code></pre>
<h3 id="解答"><a class="markdownIt-Anchor" href="#解答"></a> 解答</h3>
<pre class="highlight"><code class="python">list1 = [<span class="hljs-number">2</span>, <span class="hljs-number">11</span>, <span class="hljs-number">11</span>, <span class="hljs-number">15</span>, <span class="hljs-number">0</span>, <span class="hljs-number">0</span>, <span class="hljs-number">0</span>, <span class="hljs-number">7</span>]
target = <span class="hljs-number">9</span>
<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">find</span><span class="hljs-params">()</span>:</span>
    <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> list1:
        <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> list1[list1.index(i) + <span class="hljs-number">1</span>:]:
            <span class="hljs-keyword">if</span> i + j == target:
                <span class="hljs-keyword">return</span> print([list1.index(i), list1.index(j)])


find()
</code></pre>
<h3 id="算法-哈希字典查找"><a class="markdownIt-Anchor" href="#算法-哈希字典查找"></a> 算法 哈希字典查找</h3>
<blockquote>
<p><strong>什么是哈希图呢，python中的字典就是用的哈希图来查找，假设我们现在有5个抽屉，序号为0，1，2，3，4，现在一个对象key，经过哈希算法，会生成一个固定长度的数字，这个数字mod5，求出假如余数是1，那么这个数据value对应的就会存放在1这个抽屉中，假如这时候又一个数据余数是1，这个数据也会存放在1中，所以python中的字典不允许有两个一样的key，否则会更新这里面存储的数据</strong></p>
</blockquote>
<ol>
<li>暴力搜索法</li>
</ol>
<blockquote>
<p>我的思路就是暴力搜索法，利用两层循环结构，只要找到答案，就马上return结束</p>
</blockquote>
<ol start="2">
<li>哈希字典查找</li>
</ol>
<pre class="highlight"><code class="">list1 = [4, 11, 11, 15, 0, 4, 0, 3, 7]
target = 8
def find():
    hash = {}
    for key, value in enumerate(list1):
        if target - value in hash:
            return [hash[target - value], key]
        hash[value] = key   #这句不能放在if前面,防止target-num = num,这样就不会包括自身

print(find())
</code></pre>
<p>这里涉及到的知识：</p>
<ol>
<li>
<p>enumerate函数</p>
<pre class="highlight"><code class="">enumerate([1,2])
Out[3]: &lt;enumerate at 0x16b8c273cc8&gt;
list(enumerate([1, 2]))
Out[4]: [(0, 1), (1, 2)]
for i, n in enumerate([1,2,3]):
  ...:    print(i, n)
  ...:    
0 1
1 2
2 3
</code></pre>
</li>
<li>
<p>本题目是要寻找两数之和，并且返回下标，而字典是哈希，这样可以直接找到，即如果<code>target - num</code>在字典中，说明找到了，然后就可以直接返回</p>
</li>
<li>
<p>首先我们创建一个空的字典，然后for循环遍历，每循环一次，就往字典中加入这个数字，例如target = 9，现在有个2，则只要判断7在不在字典中即可，因为第一次为空，肯定不在的，循环一次后字典还有2，接下来假如轮到7，9-7=2，判断2是不是在字典中，发现之前字典存了2，所以直接输出就行了</p>
</li>
<li>
<p>注意这里<code>hash[value] = key</code> #这句不能放在if前面,防止<code>target-num = num</code>,这样就不会包括自身</p>
</li>
<li>
<p><code>if target - value in hash:</code>这里只能判断键在不在里面，<code>hash[value] = key</code>所以我这里换了个位置相当于2是0号位置{2：0}</p>
</li>
</ol>
<h3 id="知识补充python字典与哈希的关系"><a class="markdownIt-Anchor" href="#知识补充python字典与哈希的关系"></a> 知识补充，python字典与哈希的关系</h3>
<p>Python 调用内部的散列函数，将键（Key）作为参数进行转换，得到一个唯一的地址（这也就解释了为什么给相同的键赋值会直接覆盖的原因，因为相同的键转换后的地址是一样滴），然后将值（Value）存放到该地址中。</p>
<p>对于 Python 来说，键（Key）必须是可哈希的，换句话说就是要可以通过散列函数计算出唯一地址的。那如果拿一个变量当键（Key）可以吗？肯定不行。因为变量随时都可能改变，不符合可哈希原则！</p>
<p>同样的，列表、字典、集合这些都是可变的，所以都不能做为键（Key）来使用。</p>
<p>那有朋友可能会问，那元祖呢？元祖总该是不变的吧？</p>
<p>其实不然，因为元祖里边可以存放列表这类可变因素，所以如果实在想拿元祖当字典的键（Key），那必须对元祖做限制：元组中只包括像数字和字符串这样的不可变元素时，才可以作为字典中有效的键（Key）。</p>
<p>另外还需要注意的一点是，Python 的哈希算法对相同的值计算得到的结果是一样的，也就是说 12315 和 12315.0 的值相同，他们被认为是相同的键（Key）。</p>
<h2 id="题目三-无重复字符的最长字符串"><a class="markdownIt-Anchor" href="#题目三-无重复字符的最长字符串"></a> 题目三 无重复字符的最长字符串</h2>
<h3 id="问题"><a class="markdownIt-Anchor" href="#问题"></a> 问题</h3>
<pre class="highlight"><code class="给定一个字符串，请你找出其中不含有重复字符的">示例 1:

输入: &quot;abcabcbb&quot;
输出: 3 
解释: 因为无重复字符的最长子串是 &quot;abc&quot;，所以其长度为 3。
示例 2:

输入: &quot;bbbbb&quot;
输出: 1
解释: 因为无重复字符的最长子串是 &quot;b&quot;，所以其长度为 1。
示例 3:

输入: &quot;pwwkew&quot;
输出: 3
解释: 因为无重复字符的最长子串是 &quot;wke&quot;，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，&quot;pwke&quot; 是一个子序列，不是子串。

</code></pre>
<h3 id="算法-移动窗口"><a class="markdownIt-Anchor" href="#算法-移动窗口"></a> 算法 移动窗口</h3>
<pre class="highlight"><code class="">s = 'abcabacda'
str1 = ''
list1 = []
for each_str in s:
    if each_str not in str1:
        str1 += each_str
        list1.append(len(str1))
    else:
        str1 = str1[str1.index(each_str) + 1:] + each_str
print(max(list1))
</code></pre>
<pre class="highlight"><code class="a">ab
abc
bac
bacd
4
</code></pre>
<h3 id="错误解法"><a class="markdownIt-Anchor" href="#错误解法"></a> 错误解法</h3>
<pre class="highlight"><code class="">s = 'abcabacda'
str1 = ''
list1 = []
for each_str in s:
    if each_str not in str1:
        str1 += each_str
        list1.append(len(str1))
        print(str1)
    else:
        str1 = str1[1:] + each_str
print(max(list1))
a
ab
abc
abac
abacd
5
</code></pre>
<p>什么是移动窗口？给你一串数据，可以是列表或者字符串，设置一个小窗口，从左到右不断移动，也就是左边出，右边进，这题规定不能有重复的出现，所以<code>str1 = str1[1:] + each_str</code>这样不断左移一个是不行的<code>abac</code>必须在重复的位置，前面出现a的左边全部切掉，切掉后数据长度必定减短</p>
<p>这里附上最好的解法，运算时间和占用内存都是最低的</p>
<pre class="highlight"><code class="">s = 'abcabacd'
length, j = 0, -1
for i, x in enumerate(s):
    if x in s[j + 1:i]:
        length = max(length, i - j - 1)
        j = s[j + 1:i].index(x) + j + 1
print(max(length, len(s) - 1 - j))
</code></pre>

      
       
    </div>
</article>



<div class="article_copyright">
    <p><span class="copy-title">文章标题:</span>哈希图 and 移动窗口</p>
    <p><span class="copy-title">文章字数:</span><span class="post-count">1.5k</span></p>
    <p><span class="copy-title">本文作者:</span><a  title="Miki Zhu">Miki Zhu</a></p>
    <p><span class="copy-title">发布时间:</span>2020-03-03, 18:49:52</p>
    <p><span class="copy-title">最后更新:</span>2020-03-09, 10:30:11</p>
    <span class="copy-title">原始链接:</span><a class="post-url" href="/2020/03/03/leetcode%E7%AE%97%E6%B3%95%E7%BB%83%E4%B9%A0/" title="哈希图 and 移动窗口">http://mikiblog.online/2020/03/03/leetcode%E7%AE%97%E6%B3%95%E7%BB%83%E4%B9%A0/</a>
    <p>
        <span class="copy-title">版权声明:</span><i class="fa fa-creative-commons"></i> <a rel="license noopener" href="http://creativecommons.org/licenses/by-nc-sa/4.0/" target="_blank" title="CC BY-NC-SA 4.0 International" target = "_blank">"署名-非商用-相同方式共享 4.0"</a> 转载请保留原文链接及作者。
    </p>
</div>



    <div id="vcomment" class="comment"></div> 
<script src="//cdn1.lncld.net/static/js/3.0.4/av-min.js"></script>
<script src='//unpkg.com/valine/dist/Valine.min.js'></script>
<script src="https://cdnjs.loli.net/ajax/libs/jquery/3.2.1/jquery.min.js"></script>
<script>
    var notify = 'false' == true ? true : false;
    var verify = 'false' == true ? true : false;
    new Valine({
        av: AV,
        el: '#vcomment',
        notify: notify,
        app_id: "3uM9nFQKJdCUOHqwT3LHL5Mt-gzGzoHsz",
        app_key: "3v4CdFJJjh97olrmyHxtdDlt",
        placeholder: "请输入",
        avatar:"mm",
    });
</script>



    





  <section id="comments" class="vcomment">
  </section>

    </div>
    <div class="copyright">
        <p class="footer-entry">©2016-2019 MikiZhu 赣ICP备20004640号</p>
<p class="footer-entry">Built with <a href="https://hexo.io/" target="_blank">Hexo</a> and <a href="https://github.com/yelog/hexo-theme-3-hexo" target="_blank">3-hexo</a> theme</p>

    </div>
    <div class="full-toc">
        <button class="full"><span class="min "></span></button>
<button class="post-toc-menu"><span class="post-toc-menu-icons"></span></button>
<div class="post-toc"><span class="post-toc-title">目录</span>
    <div class="post-toc-content">

    </div>
</div>
<a class="" id="rocket" ></a>

    </div>
</div>
<div class="acParent"></div>

</body>
<script src="/js/jquery.pjax.js?v=1.0.1" ></script>

<script src="/js/script.js?v=1.0.1" ></script>
<script>
    var img_resize = 'default';
    /*作者、标签的自动补全*/
    $(function () {
        $('.search').AutoComplete({
            'data': ['#机器学习','#算法','#博客搭建','#python','#网站推荐','#考研经验',],
            'itemHeight': 20,
            'width': 418
        }).AutoComplete('show');
    })
    function initArticle() {
        /*渲染对应的表格样式*/
        
            $(".post .pjax table").addClass("green_title");
        

        /*渲染打赏样式*/
        

        /*高亮代码块行号*/
        

        /*访问数量*/
        
        $.getScript("//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js");
        

        /*代码高亮，行号对齐*/
        $('.pre-numbering').css('line-height',$('.has-numbering').css('line-height'));

        
        
    }

    /*打赏页面隐藏与展示*/
    

</script>

<!--加入行号的高亮代码块样式-->

<!--自定义样式设置-->
<style>
    
    
    .nav {
        width: 542px;
    }
    .nav.fullscreen {
        margin-left: -542px;
    }
    .nav-left {
        width: 120px;
    }
    
    
    @media screen and (max-width: 1468px) {
        .nav {
            width: 492px;
        }
        .nav.fullscreen {
            margin-left: -492px;
        }
        .nav-left {
            width: 100px;
        }
    }
    
    
    @media screen and (max-width: 1024px) {
        .nav {
            width: 492px;
            margin-left: -492px
        }
        .nav.fullscreen {
            margin-left: 0;
        }
        .nav .hide-list.fullscreen {
            left: 492px
        }
    }
    
    @media screen and (max-width: 426px) {
        .nav {
            width: 100%;
        }
        .nav-left {
            width: 100%;
        }
    }
    
    
    .nav-right .title-list nav a .post-title, .nav-right .title-list #local-search-result a .post-title {
        color: #383636;
    }
    
    
    .nav-right .title-list nav a .post-date, .nav-right .title-list #local-search-result a .post-date {
        color: #5e5e5f;
    }
    
    
    .nav-right nav a.hover, #local-search-result a.hover{
        background-color: #e2e0e0;
    }
    
    

    /*列表样式*/
    
    .post .pjax article .article-entry>ol, .post .pjax article .article-entry>ul, .post .pjax article>ol, .post .pjax article>ul{
        border: #e2dede solid 1px;
        border-radius: 10px;
        padding: 10px 32px 10px 56px;
    }
    .post .pjax article .article-entry li>ol, .post .pjax article .article-entry li>ul,.post .pjax article li>ol, .post .pjax article li>ul{
        padding-top: 5px;
        padding-bottom: 5px;
    }
    .post .pjax article .article-entry>ol>li, .post .pjax article .article-entry>ul>li,.post .pjax article>ol>li, .post .pjax article>ul>li{
        margin-bottom: auto;
        margin-left: auto;
    }
    .post .pjax article .article-entry li>ol>li, .post .pjax article .article-entry li>ul>li,.post .pjax article li>ol>li, .post .pjax article li>ul>li{
        margin-bottom: auto;
        margin-left: auto;
    }
    

    /* 背景图样式 */
    
    


    /*引用块样式*/
    

    /*文章列表背景图*/
    
    .nav-right:before {
        content: ' ';
        display: block;
        position: absolute;
        left: 0;
        top: 0;
        width: 100%;
        height: 100%;
        opacity: 0.4;
        background: url("http://q8idlsxje.bkt.clouddn.com/%E6%B5%B7%E6%BB%A9.jpg");
        background-repeat: no-repeat;
        background-position: 50% 0;
        -ms-background-size: cover;
        -o-background-size: cover;
        -moz-background-size: cover;
        -webkit-background-size: cover;
        background-size: cover;
    }
    

    
</style>







  <script src="//cdn1.lncld.net/static/js/3.0.4/av-min.js"></script>
  <script src="//unpkg.com/valine/dist/Valine.min.js"></script>
  <script>
    var GUEST_INFO = ['nick','mail','link'];
    var guest_info = 'nick,mail,link'.split(',').filter(function(item){
        return GUEST_INFO.indexOf(item) > -1
    });
    var notify = 'false' == true;
    var verify = 'false' == true;
    new Valine({
      el: '.vcomment',
      notify: notify,
      verify: verify,
      appId: "3uM9nFQKJdCUOHqwT3LHL5Mt-gzGzoHsz",
      appKey: "3v4CdFJJjh97olrmyHxtdDlt",
      placeholder: "请输入",
      pageSize: '10',
      avatar: 'mm',
      lang: 'zh-cn',
      visitor: 'true'
    });
  </script>

</html>
